526G - Spiders Evil Plan - CodeForces Solution

# include <cstdio>
# include <algorithm>
# include <cmath>
# include <iostream>
# include <cstring>
# include <vector>
# include <map>
# include <set>
# include <queue>
using namespace std;
const int MAXN = 1e6 + 7, mod = 1e9 + 7;
int n, q, lst;
vector <pair <int, int> > g[MAXN];
struct tree {
	int rt, fa[MAXN], hv[MAXN], mx[MAXN], d[MAXN], p[MAXN], col[MAXN], up[20][MAXN], tp;
	long long ans[MAXN];
	void dfs(int u) {
		for (auto [v, w] : g[u]) if (v != fa[u]) {
			fa[v] = u, d[v] = d[u] + w, dfs(v), mx[v] += w;
			if (mx[u] < mx[v]) mx[u] = mx[v], hv[u] = v;
		}
	}
	void init() {
		dfs(rt);
		for (int i = 1; i <= n; i++) if (hv[fa[i]] != i) p[++tp] = i;
		sort(p + 1, p + tp + 1, [&](int x, int y) { return mx[x] > mx[y]; });
		for (int i = 1; i <= tp; i++) {
			ans[i] = ans[i - 1] + mx[p[i]];
			for (int u = p[i]; u; u = hv[u]) col[u] = i;
		}
		for (int i = 1; i <= n; i++) up[0][i] = fa[i];
		for (int i = 1; i <= 19; i++) 
			for (int j = 1; j <= n; j++) up[i][j] = up[i - 1][up[i - 1][j]];
	}
	int gv(int x, int k) {
		for (int i = 19; i >= 0; i--)
			if (col[up[i][x]] > k) x = up[i][x];
		return fa[x];
	}
	int query(int x, int y) {
		y = y * 2 - 1;
		if (y > tp) return ans[tp];
		if (col[x] <= y) return ans[y];
		int z = p[col[gv(x, y)]];
		return max(ans[y - 1] + d[x] + mx[hv[x]] - d[gv(x, y - 1)], ans[y] - mx[z] + (d[x] - d[fa[z]] + mx[hv[x]]));
	}
} t1, t2;
int v1, v2, d[MAXN];
int get() {
	int mx = *max_element(d + 1, d + n + 1);
	for (int i = 1; i <= n; i++) if (d[i] == mx) return i;
}
void dfs(int u, int fa) {
	for (auto [v, w] : g[u]) if (v != fa) d[v] = d[u] + w, dfs(v, u);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back(make_pair(v, w));
		g[v].push_back(make_pair(u, w));
	}
	dfs(1, 0), v1 = get();
	dfs(v1, 0), v2 = get();
	t1.rt = v1, t1.init();
	t2.rt = v2, t2.init();
	while (q--) {
		int x, y;
		cin >> x >> y;
		x = (x + lst - 1) % n + 1;
		y = (y + lst - 1) % n + 1;
		cout << (lst = max(t1.query(x, y), t2.query(x, y))) << "\n" ;
	}
	return 0;
}